
struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* partition(struct ListNode* head, int x){
    struct ListNode *ret = NULL;
    struct ListNode *bNode = NULL;
    struct ListNode *eNode = head;

    if (head == NULL) {
        return NULL;
    }

    if (head->val < x) {
        ret = head;
        bNode = head;

        while (head) {
            if (head->next) {
                if (head->next->val >= x) {
                    bNode = head;
                    eNode = head->next;
                    break;
                }
            } else {
                return ret;
            }

            head = head->next;
        }
    } else {
        ret = NULL;
        bNode = NULL;
        eNode = head;
    }

    struct ListNode *curPre = NULL;
    struct ListNode *curNode = NULL;
    struct ListNode *curNext = NULL;
    curPre = eNode;
    curNode = eNode->next;
    while (curNode) {
        curNext = curNode->next;

        if (curNode->val < x) {
            if (bNode) {
                bNode->next = curNode;
            } else {
                ret = curNode;
            }
            bNode = curNode;
            curPre->next = curNext;
            curNode->next = eNode;
        } else {
            curPre = curNode;
        }

        curNode = curNext;
    }

    if (ret == NULL) {
        ret = eNode;
    }

    return ret;
}
